#include <vector>
using namespace std;
bool binary_search(const vector<vector<int>> &matrix, int target, int row,
                   int cols) {
  int left = 0;
  int right = cols - 1;
  while (left <= right) {
    int mid = (left + right) / 2;
    if (matrix[row][mid] == target) {
      return true;
    }
    if (matrix[row][mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return false;
}
bool searchMatrix(vector<vector<int>> &matrix, int target) {
  int rows = matrix.size();
  int cols = matrix[0].size();
  if (rows * cols == 1) {
    return matrix[0][0] == target;
  }
  for (int i = rows - 1; i >= 0; i--) {
    if (target >= matrix[i][0] && target <= matrix[i][cols - 1]) {
      return binary_search(matrix, target, i, cols);
    }
  }
  return false;
}